package leetcode;

public class ThirdMaximumNumber {

	public static void main(String[] args) {
		ThirdMaximumNumber object = new ThirdMaximumNumber();
		int[] nums = {1, 2};
		int[] nums1 = {1, 2, 2};
		int[] nums2 = {3, 2, 2, 1};
		int[] nums3 = {3, 3, 2, 2};
		int[] nums4 = {3, 3, 3, 2};
		int[] nums5 = {3, 3, 3, 3};
		int[] nums6 = {Integer.MIN_VALUE, 1, 2, Integer.MIN_VALUE};
		
		object.thirdMax2(nums);
		System.out.println(object.thirdMax2(nums1));
		object.thirdMax2(nums2);
		object.thirdMax2(nums3);
		object.thirdMax2(nums4);
		object.thirdMax2(nums5);
		System.out.println(object.thirdMax2(nums6));
	}
	
	public int thirdMax(int[] nums) {
		if (nums == null) {
			return -1;
		}
		int max = Integer.MIN_VALUE;
		int secondMax = Integer.MIN_VALUE;
		int thirdMax = Integer.MIN_VALUE;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] > max) {
				if(secondMax != Integer.MIN_VALUE){
					thirdMax = secondMax;
				}
				secondMax = max;
				max = nums[i];
			} else if (nums[i] > secondMax) {
				if(nums[i] == max){
					continue;
				}
				if(secondMax != Integer.MIN_VALUE){
					thirdMax = secondMax;
				}
				secondMax = nums[i];
			} else if (nums[i] > thirdMax) {
				if(nums[i] != secondMax){
					thirdMax = nums[i];
				}
			}
		}
		System.out.println(max + "  " + secondMax + "  " + thirdMax);
		return thirdMax;
	}
	
	//由于在数组中可能出现最小值，所以上面的方法无法通过
	public int thirdMax2(int[] nums) {
		if (nums == null) {
			return -1;
		}
		Integer max = null;
		Integer secondMax = null;
		Integer thirdMax = null;
		for (int i = 0; i < nums.length; i++) {
			if (max == null || nums[i] > max) {
				if(secondMax != null){
					thirdMax = secondMax;
				}
				secondMax = max;
				max = nums[i];
			} else if (secondMax == null || nums[i] > secondMax) {
			    if(nums[i] == max){
					continue;
				}
				if(secondMax != null){
					thirdMax = secondMax;
				}
				secondMax = nums[i];
			} else if (thirdMax == null || nums[i] > thirdMax) {
				if(nums[i] != secondMax){
					thirdMax = nums[i];
				}
			}
		}
		System.out.println(max + "  " + secondMax + "  " + thirdMax);
		return thirdMax == null ? max : thirdMax;
	}
}
